/* =============================================================
 * Your Grandmother's guide to Algorithms
 * =============================================================
 *
 * Copyright (c) 2007, Saverio Miroddi
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 * 
 *     * Redistributions of source code must retain the above copyright notice,
 *       this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright 
 *       notice, this list of conditions and the following disclaimer in the 
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the <ORGANIZATION> nor the names of its 
 *       contributors may be used to endorse or promote products derived from 
 *       this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *  
 * ---------------------------
 * RabinKarp.java
 * ---------------------------
 *
 */
package strmatching;

import java.util.Arrays;

/**
 * Basic implementation of the Rabin-Karp string matching algorithms.<br>
 * Watch out! The hash function is appropriate, but a more complex
 * implementation must be used to support long patterns, because the current
 * bombs when too high overflows happen ({@link RabinKarp#rollHash(byte, byte, int, int)}).
 * 
 * @author Saverio Miroddi
 */
public class RabinKarp
{
	/**
	 * Find the first occurence of the pattern inside the source string.
	 * 
	 * @param source
	 *            source sequence.
	 * @param pattern
	 *            pattern string, not longer thatn
	 * @return position, 0-based; -1 if not found.
	 */
	public static int match(byte[] source, byte[] pattern)
	{
		if (source.length < pattern.length) {
			return -1;
		}
		else {
			int pattHash = firstHash(pattern);
			int seqHash = firstHash(Arrays.copyOf(source, pattern.length));
			
			for (int i = 0; i <= source.length - pattern.length; i++) {
				if (i > 0) {
					byte nextByte = source[i + pattern.length - 1];
					byte discardedBye = source[i - 1];
					seqHash = rollHash(nextByte, discardedBye, seqHash, pattern.length);
				}
				 
				boolean collision = (seqHash == pattHash);
				
				if (collision) {
					boolean matching = isByteMatching(source, i, pattern);
					
					if (matching) return i;					
				}
			}
			
			return -1;
		}
	}
	
	private static boolean isByteMatching(byte[] source, int i, byte[] pattern)
	{
		byte[] sourceSubstr = Arrays.copyOfRange(source, i, i + pattern.length);
		return Arrays.equals(sourceSubstr, pattern);
	}

	//////////////////////////////////////////////////////////////////////////
	// HASH PART
	//////////////////////////////////////////////////////////////////////////
	
	private static final int HASH_CONST = 101; // like Wikipedia
	
	/** 
	 * Rollable hash, limited to about 5 character.
	 */
	private static int firstHash(byte[] sequence)
	{
		if (sequence.length > 5) throw new IllegalArgumentException("This hash fx isn't designed for long patterns.");
		
		int hash = 0;
		
		for (int i = 0; i < sequence.length; i++) {
			int factor = (int)Math.pow(HASH_CONST, sequence.length - i - 1);
			hash += sequence[i] * factor;
		}
		
		return hash;
	}

	/** Perform the rolling. */
	private static int rollHash(
			byte nextByte, byte discardedByte, int oldHash, int patternLen)
	{
		oldHash -= discardedByte * (int)Math.pow(HASH_CONST, patternLen - 1);
		
		oldHash *= HASH_CONST;
		
		oldHash += nextByte; // * HASH_CONST ** 0 
		
		return oldHash;
	}
}